'''
https://leetcode.cn/problems/word-ladder-ii/description/
'''
import string
from collections import defaultdict, deque
from typing import List


class Solution:

    def build(self, words, begin_word):
        res = defaultdict(list)
        for word in words:
            for i in range(len(word)):
                old_char = word[i]
                for char in string.ascii_lowercase:
                    if char == old_char: continue
                    new_word = word[:i] + char + word[i+1:]
                    if new_word in words:
                        res[word].append(new_word)
        return res

    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        words = set(wordList)
        words.add(beginWord)
        if endWord not in words: return []
        graph = self.build(words, endWord)
        distance = defaultdict(lambda: float('inf'))
        distance[endWord] = 1
        q = deque([endWord])
        while q:
            u = q.popleft()
            if distance[u] == distance[beginWord]:
                continue
            for v in graph[u]:
                if distance[u] + 1 < distance[v]:
                    distance[v] = distance[u] + 1
                    q.append(v)
        if distance[beginWord] == float('inf'):
            return []
        res = []
        path = [beginWord]
        def dfs(u):
            if u == endWord:
                res.append(path[:])
                return
            for v in graph[u]:
                if distance[v] == distance[u] - 1:
                    path.append(v)
                    dfs(v)
                    path.pop()
        dfs(beginWord)
        return res



beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","tog","cog"]

print(Solution().findLadders(beginWord, endWord, wordList))